Token bucket

The token bucket is an algorithm used in packet switched computer networks and telecommunications networks to check that data transmissions conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow).

The token bucket algorithm is based on an analogy of a bucket that contains tokens, each of which can represent a unit of bytes or a single packet of predetermined size. When a packet is to be checked for conformance to the defined limits, the bucket is inspected to see if it contains sufficient tokens at that time. If so, the appropriate number of tokens, e.g. equivalent to the length of the packet in bytes, are removed ("cashed in"), and the packet is passed, e.g., for transmission. If there are insufficient tokens in the bucket the packet does not conform and the contents of the bucket are not changed. Non-conformant packets can be treated in various ways:

A conforming flow can thus contain traffic up to its peak burst rate if there are adequate tokens in the bucket and if the depth of the bucket is set appropriately.

Contents

The token bucket algorithm

The algorithm can be conceptually understood as follows:

Variations

Implementers of this algorithm on platforms lacking the clock resolution necessary to add a single token to the bucket every 1/r seconds may want to consider an alternative formulation. Given the ability to update the token bucket every S milliseconds, the number of tokens to add every S milliseconds = (r*S)/1000.

Properties

Average rate

Over the long run the output of conformant packets is limited by the token rate, r.

Burst size

Let M be the maximum possible transmission rate in bytes/second.

Then T_\text{max} = \begin{cases} b/(M -r) & \text{ if } r < M \\ \infty & \text{ otherwise } \end{cases} is the maximum burst time, that is the time for which the rate M is fully utilized.

The maximum burst size is thus L_\text{max} = T_\text{max}*M

Uses

The token bucket can be used in either traffic shaping or traffic policing. In traffic policing, nonconforming packets may be discarded (dropped) or may be reduced in priority (for downstream traffic management functions to drop if there is congestion). In traffic shaping, packets are delayed until they conform. Traffic policing and traffic shaping are commonly used to protect the network against excess or excessively bursty traffic, see bandwidth management and congestion avoidance. Traffic shaping is commonly used in the network interfaces in hosts to prevent transmissions being discarded by traffic management functions in the network.

Comparison to leaky bucket

The token bucket algorithm is directly comparable to one of the two versions of the leaky bucket algorithm described in the literature[1][2][3][4]. This comparable version of the leaky bucket is described on the relevant Wikipedia page as the leaky bucket algorithm as a meter. This is a mirror image of the token bucket, in that conforming packets add fluid, equivalent to the tokens, to a finite capacity bucket, from which this fluid then drains away at a constant rate, equivalent to the process in the token bucket algorithm in which tokens are added at a fixed rate.

There is, however, another version of the leaky bucket algorithm[2], described on the relevant Wikipedia page as the leaky bucket algorithm as a queue. This is a special case of the leaky bucket as a meter, which can be described by the conforming packets passing through the bucket. The leaky bucket as a queue is therefore applicable only to traffic shaping, and does not, in general, allow the output packet stream to be bursty, i.e. it is jitter free. It is therefore significantly different from the token bucket algorithm.

These two versions of the leaky bucket algorithm have both been described in the literature under the same name. This has led to considerable confusion over the properties of that algorithm and its comparison with the token bucket algorithm. However, fundamentally, the two algorithms are the same, and will, if implemented correctly and given the same parameters, see exactly the same packets as conforming and nonconforming.

Hierarchical token bucket

The Hierarchical Token Bucket (HTB) is a faster replacement for the class-based queueing qdisc (queuing discipline) in Linux[5].

Description

HTBs help in controlling the use of the outbound bandwidth on a given link. HTB allows using one single physical link to simulate multiple slower links and to send different kinds of traffic on different simulated links. In both cases, one has to specify how to divide the physical link into simulated links and how to decide which simulated link a given packet is to be sent across.

In other words, HTB is very useful to limit a client's download/upload rate. Thus, the limited client cannot saturate the total bandwidth.

References

  1. ^ Turner, J., New directions in communications (or which way to the information age?). Communications Magazine, IEEE 24 (10): 8–15. ISSN 0163-68041986.
  2. ^ a b Andrew S. Tanenbaum, Computer Networks, Fourth Edition, ISBN 0-13-166836-6, Prentice Hall PTR, 2003., page 401.
  3. ^ ATM Forum, The User Network Interface (UNI), v. 3.1, ISBN 0-13-393828-X, Prentice Hall PTR, 1995.
  4. ^ ITU-T, Traffic control and congestion control in B ISDN, Recommendation I.371, International Telecommunication Union, 2004, Annex A, page 87.
  5. ^ Linux HTB Home Page http://luxik.cdi.cz/~devik/qos/htb/ ...

See also